package com.heima.leetcode.practice;

/**
 * leetcode 121. 买卖股票的最佳时机
 * @author 勾新杰
 * @version 1.0
 * @date 2024/11/5 9:58
 */
public class E121 {

    /**
     * <h3>方法一：穷举法，会超出时间限制</h3>
     * @param prices 股票价格数组
     * @return 最大利润
     */
    public int maxProfit1(int[] prices) {
        int maxProfit = 0;
        for (int i = 0; i < prices.length; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                if (prices[j] > prices[i]){
                    maxProfit = Math.max(maxProfit, prices[j] - prices[i]);
                }
            }
        }
        return maxProfit;
    }

    /**
     * <h3>方法二：一次遍历，for循环，动态更新当前遇到的最小价格</h3>
     * @param prices 股票价格数组
     * @return 最大利润
     */
    public int maxProfit2(int[] prices) {
        int maxProfit = 0; // 最大利润
        int minPrice = Integer.MAX_VALUE; // 当前遇到的最小价格
        for (int price : prices) {
            if (price < minPrice){
                minPrice = price; // 当前是遇到了更小的最小价格，这一天肯定不可能卖出股票，亏损最大化
            } else if (price - minPrice > maxProfit) { // 当前价格比最小价格大，则可以考虑卖出股票，但是要看是否能赚取最大利润
                maxProfit = price - minPrice;
            }
        }
        return maxProfit;
    }

    /**
     * <h3>方法三：一次遍历，fori循环，动态更新当前遇到的最小价格</h3>
     * @param prices 股票价格数组
     * @return 最大利润
     */
    public int maxProfit3(int[] prices) {
        int maxProfit = 0, minPrice = prices[0];
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] < minPrice) minPrice = prices[i];
            else if (prices[i] > minPrice) maxProfit = Math.max(maxProfit, prices[i] - minPrice);
        }
        return maxProfit;
    }
}
